package sort;

import sun.security.util.Length;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author huangxin
 * @date 2019/6/25-9:37
 */
public class QuickSort {

    public static void quick(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int temp;
        int pivot = arr[(left + right) / 2];
        while (l <= r) {
            while (arr[l] < pivot) {
                l++;
            }
            while (arr[r] > pivot) {
                r--;
            }

            if (l <= r) {
                //交换
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;

                l++;
                r--;
            }

        }

        if (left < r) {
            quick(arr, left, r);
        }

        if (right > l) {
            quick(arr, l, right);
        }
    }


    public static void quick2(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int temp;
        int pivot = arr[(left + right) / 2];
        while (l <= r) {
            while (arr[l] < pivot) {
                l++;
            }
            while (arr[r] > pivot) {
                r--;
            }


            if (l <= r) {
                //交换
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;

                l++;
                r--;
            }


        }

        if (l < right) {
            quick2(arr, l, right);
        }

        if (r > left) {
            quick2(arr, left, r);
        }

    }
}
